#include <string>
#include <unordered_set>
#include <unordered_map>
#include <climits>
#include <algorithm>
#include <functional>
#include <queue>
#include <iostream>
#include <tuple>
#include <map>
#include <set>

size_t dif(const std::string& s1, const std::string& s2)
{
	size_t dif = 0;
	for (size_t i = 0; i < s1.size(); i++)
		if (s1[i] != s2[i]) dif++;
	return dif;
}

struct BFS
{
	const std::string& m_word;
	const std::unordered_set<std::string>& m_wordList;
	
	std::unordered_set<std::string> m_thisLevel;
	std::unordered_set<std::string> m_nextLevel;

	// node not to be detected, including this level
	std::unordered_set<std::string> m_closedSet;

	std::map<std::string, std::set<std::string>> m_cameFrom;

	BFS(const std::string& word, const std::unordered_set<std::string>& wordList) :
		m_word(word),
		m_wordList(wordList)
	{
		m_thisLevel.insert(m_word);
		m_closedSet.insert(m_word);
	}

	bool iterate()
	{
		for (const auto& word : m_thisLevel) {
			for (size_t i = 0; i < word.size(); i++) {
				for (auto ch = 'a'; ch <= 'z'; ch++) {
					std::string neighbor = word;
					neighbor[i] = ch;
					if (m_closedSet.count(neighbor) == 0 && m_wordList.count(neighbor) == 1) {
						m_nextLevel.insert(neighbor);
						m_cameFrom[neighbor].insert(word);
					}
				}
			}
		}
		if (m_nextLevel.empty()) {
			return false;
		} else {
			m_thisLevel = std::move(m_nextLevel);
			for (const auto& word : m_thisLevel)
				m_closedSet.insert(word);
			return true;
		}
	}

	std::vector<std::string> intersect(const BFS& other)
	{
		std::vector<std::string> result;
		for (const auto& word : m_thisLevel) {
			if (other.m_thisLevel.count(word) != 0) {
				result.emplace_back(word);
			}
		}
		return result;
	}

	std::vector<std::vector<std::string>> constructPathes(const std::string& word)
	{
		std::vector<std::vector<std::string>> pathes;
		std::vector<std::string> path;
		std::function<void(const std::string&)> construct = [&](const std::string& current)
		{
			path.emplace_back(current);
			if (m_cameFrom.count(current) == 0) {
				pathes.emplace_back(path);
			} else {
				for (const auto& next : m_cameFrom[current]) {
					construct(next);
				}
			}
			path.pop_back();
		};
		construct(word);
		return pathes;
	}
};

class Solution
{
public:
	std::vector<std::vector<std::string>> 
		findLadders(
		std::string beginWord, 
		std::string endWord, 
		std::unordered_set<std::string> &wordList)
	{
		wordList.insert(beginWord);
		wordList.insert(endWord);
		std::vector<std::string> insersection;
		BFS front{ beginWord, wordList };
		BFS back{ endWord, wordList };
		while (true) {
			if (!front.iterate()) break;
			insersection = front.intersect(back);
			if (!insersection.empty()) break;

			if (!back.iterate()) break;
			insersection = front.intersect(back);
			if (!insersection.empty()) break;
		}
		std::vector<std::vector<std::string>> pathes;
		for (const auto& word : insersection) {
			auto frontPathes = front.constructPathes(word);
			auto backPathes = back.constructPathes(word);
			for (auto& frontPath : frontPathes) {
				for (auto& backPath : backPathes) {
					std::vector<std::string> path = frontPath;
					std::reverse(path.begin(), path.end());
					path.pop_back();
					path.insert(path.cend(), backPath.cbegin(), backPath.cend());
					pathes.emplace_back(std::move(path));
				}
			}
		}
		return pathes;
	}
};

int main()
{
	std::unordered_set<std::string> wordList{ "hot", "dot", "dog", "lot", "log" };
	auto results = Solution().findLadders("hit", "cog", wordList);
	for (const auto& result : results) {
		for (const auto& word : result) {
			std::cout << word << ' ';
		}
		std::cout << std::endl;
	}
	system("pause");
	return 0;
}